#include<stdio.h>
#include<stdlib.h>

void MergeS(int arr[], int tmp[], int start, int mid, int end) {
	int i = start;
	int j = mid + 1;
	int k = start;
	while (i <= mid && j <= end) {
		if (arr[i] <= arr[j]) {
			tmp[k++] = arr[i++];
		}
		else {
			tmp[k++] = arr[j++];
		}
	}
	while (i <= mid) {
		tmp[k++] = arr[i++];
	}
	while (j <= end) {
		tmp[k++] = arr[j++];
	}
	for (i = start; i <= end; i++) {
		arr[i] = tmp[i];
	}
}

void MergeSort(int arr[], int len) {
	int* tmp = (int*)malloc(sizeof(int) * len);
	int mid = len / 2;
	MergeS(arr, tmp, 0, mid,len - 1);
	free(tmp);
}

int main() {
	int arr[] = { 12, 3, 21, 32, 1, 34, 12, 35, 34 };
	int len = sizeof(arr) / sizeof(arr[0]);
	MergeSort(arr, len);
	for (int i = 0; i < len; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}